//
// Created by edward on 23-2-10.
//

#ifndef CONCURRENCE_LOCKFREESTACK_H
#define CONCURRENCE_LOCKFREESTACK_H

#include <memory>
#include <atomic>

namespace edward::multithread {

    template<typename T>
    class LockFreeStack {
        using Ptr = std::shared_ptr<T>;
        struct Node;
        using NodePtr = std::shared_ptr<Node>;
    public:

        void push(T t) {
            NodePtr node = std::make_shared<Node>(std::make_shared<T>(std::move(t)), head_.load());
            while (!head_.compare_exchange_weak(node->next_, node));
        }

        Ptr pop() {
            NodePtr head = head_.load();
            while(head && !head_.compare_exchange_weak(head, head->next_));
            Ptr ret; //空栈返回空指针

            //从节点提取数据，节点可能不立即删除，但是如果返回的数据一旦不需要(例如不保存返回值)就立即被删除
            if (head) {
                head->next_ = NodePtr{};
                ret.swap(head->data_);
            }

            return ret;
        }

    private:
        struct Node {
            Ptr data_;
            NodePtr next_;
            Node(Ptr data, NodePtr next = nullptr)
                    : data_(data)
                    , next_(next)
            {}
        };
        std::atomic<NodePtr> head_ = nullptr;     //链表头节点，用来模拟栈
    };

}

#endif //CONCURRENCE_LOCKFREESTACK_H
